import java.util.Arrays;

/**
 * Memory-efficient hash map for storing <int, int> key-value pairs. Shows
 * comparable performance to build-in HashMap<Integer, Integer>.
 * 
 * @author Denis Kulagin
 * 
 */
public class HashIntIntMap {
	public static final int DEFAULT_BUCKET_COUNT = 255;
	public static final int DEFAULT_INITIAL_CAPACITY = 128;
	public static final double DEFAULT_MAX_LOAD_FACTOR = 0.9;
	public static final double DEFAULT_CAPACITY_EXPAND_FACTOR = 1.2;

	private int initialBucketCapacity = DEFAULT_INITIAL_CAPACITY;
	private double maxLoadFactor = DEFAULT_MAX_LOAD_FACTOR;
	private double capacityExpandFactor = DEFAULT_CAPACITY_EXPAND_FACTOR;

	private class Bucket {
		private static final byte EMPTY = 0;
		private static final byte OCCUPIED = 1;
		private static final byte DELETED = 2;

		private int size;

		private byte[] status;
		private int[] keys;
		private int[] values;

		private int criticalSize;

		public Bucket() {
			init(HashIntIntMap.this.initialBucketCapacity);
		}

		private void init(int capacity) {
			size = 0;
			status = new byte[capacity];
			Arrays.fill(status, EMPTY);
			keys = new int[capacity];
			values = new int[capacity];
			criticalSize = (int) (keys.length * HashIntIntMap.this.maxLoadFactor);
		}

		private int computeIndex(int key) {
			return Math.abs(key) % keys.length;
		}

		private int computeNextIndex(int index) {
			return (index + 1) % keys.length;
		}

		private boolean unsafePut(int key, int value) {
			int index = computeIndex(key);
			while (status[index] == OCCUPIED && keys[index] != key) {
				index++;
				if (index >= keys.length) {
					index = 0;
				}
			}
			boolean hasOverwrittenOldValue = status[index] == OCCUPIED;
			status[index] = OCCUPIED;
			keys[index] = key;
			values[index] = value;
			size++;
			return !hasOverwrittenOldValue;
		}

		public boolean put(int key, int value) {
			while (size > criticalSize) {
				expand();
			}

			return unsafePut(key, value);
		}

		private void expand() {
			int oldCapacity = keys.length;
			byte[] oldStatus = status;
			int[] oldKeys = keys;
			int[] oldValues = values;

			int newCapacity = (int) Math.round(oldCapacity
					* HashIntIntMap.this.capacityExpandFactor);
			init(newCapacity);

			for (int index = 0; index < oldCapacity; index++) {
				if (oldStatus[index] == OCCUPIED) {
					unsafePut(oldKeys[index], oldValues[index]);
				}
			}
		}

		private int locateKey(int key) {
			int index = computeIndex(key);
			int initialIndex = index;
			do {
				if (status[index] == DELETED || status[index] == OCCUPIED
						&& keys[index] != key) {
					index++;
					if (index >= keys.length) {
						index = 0;
					}
				} else if (status[index] == OCCUPIED && keys[index] == key) {
					return index;
				} else {
					return -1;
				}
			} while (index != initialIndex);
			return -1;
		}

		public int getInt(int key) throws NoSuchKeyExistsException {
			int index = locateKey(key);
			if (index != -1) {
				return values[index];
			} else {
				throw new NoSuchKeyExistsException();
			}
		}

		public Integer get(int key) {
			int index = locateKey(key);
			if (index != -1) {
				return new Integer(values[index]);
			} else {
				return null;
			}
		}

		public boolean containsKey(int key) {
			return locateKey(key) != -1;
		}

		public Integer remove(int key) {
			int index = computeIndex(key);
			boolean found = false;
			while (!found) {
				if (status[index] == OCCUPIED && keys[index] == key) {
					status[index] = DELETED;
					size--;
					return new Integer(values[index]);
				} else if (status[index] == DELETED
						|| status[index] == OCCUPIED && keys[index] != key) {
					index = computeNextIndex(index);
				} else {
					return null;
				}
			}
			return null;
		}
	}

	private Bucket[] buckets;
	private int size = 0;

	/**
	 * Creates new hash map, containing ints as keys and ints as values.
	 * 
	 * Sets number of buckets to default value.
	 */
	public HashIntIntMap() {
		initBuckets(DEFAULT_BUCKET_COUNT);
	}

	/**
	 * 
	 * Creates new hash map, containing ints as keys and ints as values.
	 * 
	 * Sets number of buckets to specified value. It's recommended, that number
	 * of buckets to be set as 2^n - 1 to lower number of collisions.
	 * 
	 * @param bucketCount
	 *            number of buckets
	 */
	public HashIntIntMap(int bucketCount) {
		initBuckets(bucketCount);
	}

	/**
	 * Creates new hash map, containing ints as keys and ints as values.
	 * 
	 * Sets number of buckets to specified value. It's recommended, that number
	 * of buckets to be set as 2^n - 1 to lower number of collisions.
	 * 
	 * @param bucketCount
	 *            number of buckets
	 * @param initialBucketCapacity
	 *            initial capacity of each bucket
	 */
	public HashIntIntMap(int bucketCount, int initialBucketCapacity) {
		this.initialBucketCapacity = initialBucketCapacity;
		initBuckets(bucketCount);
	}

	/**
	 * Creates new hash map, containing ints as keys and ints as values.
	 * 
	 * Sets number of buckets to specified value. It's recommended, that number
	 * of buckets to be set as 2^n - 1 to lower number of collisions.
	 * 
	 * It's possible to tune maxLoadFactor and capacityExpandFactor.
	 * 
	 * @param bucketCount
	 *            number of buckets
	 * @param initialBucketCapacity
	 *            initial capacity of each bucket
	 * @param maxLoadFactor
	 *            maximal load factor value, after which bucket internal array
	 *            to be expanded
	 * @param capacityExpandFactor
	 *            when number of elements in the bucket will exceed threshold,
	 *            bucket internal array will be expanded and newCapacity =
	 *            oldCapacity * capacityExpandFactor
	 */
	public HashIntIntMap(int bucketCount, int initialBucketCapacity,
			double maxLoadFactor, double capacityExpandFactor) {
		this.initialBucketCapacity = initialBucketCapacity;
		this.maxLoadFactor = maxLoadFactor;
		this.capacityExpandFactor = capacityExpandFactor;
		initBuckets(bucketCount);
	}

	/**
	 * Puts <key, value> pair in the map. If specified key already exists in the
	 * map, assigned value is overwritten with new one.
	 * 
	 * @param key
	 *            key
	 * @param value
	 *            value
	 * @return true, if map hasn't contained a key or false, if old value has
	 *         been overwritten
	 */
	public boolean put(int key, int value) {
		int bucketIndex = computeBucketIndex(key);
		if (buckets[bucketIndex].put(key, value)) {
			size++;
			return true;
		} else {
			return false;
		}
	}

	/**
	 * Returns value assigned with specified key. If key doesn't exist in the
	 * map, exception is thrown.
	 * 
	 * @param key
	 *            key
	 * @return value
	 * @throws NoSuchKeyExistsException
	 */
	public int getInt(int key) throws NoSuchKeyExistsException {
		int bucketIndex = computeBucketIndex(key);
		return buckets[bucketIndex].getInt(key);
	}

	/**
	 * Returns Integer wrapper to int assigned with the key. If key doesn't
	 * exist in the map, null is returned.
	 * 
	 * @param key
	 *            key
	 * @return value wrapped in Integer or null, if key doesn't exists in the
	 *         table
	 */
	public Integer get(int key) {
		int bucketIndex = computeBucketIndex(key);
		return buckets[bucketIndex].get(key);
	}

	/**
	 * Checks, if specified key is in the map's keyset.
	 * 
	 * @param key
	 *            key
	 * @return true, if key exists or false otherwise
	 */
	public boolean containsKey(int key) {
		int bucketIndex = computeBucketIndex(key);
		return buckets[bucketIndex].containsKey(key);
	}

	/**
	 * Removes key and it's assigned value from the map.
	 * 
	 * @param key
	 *            key
	 * @return old value or null, if key hasn't exist in the map
	 */
	public Integer remove(int key) {
		int bucketIndex = computeBucketIndex(key);
		Integer value = buckets[bucketIndex].remove(key);
		if (value != null) {
			size--;
		}
		return value;
	}

	/**
	 * Returns size of the map's keyset.
	 * 
	 * @return size of the map's keyset
	 */
	public int size() {
		return size;
	}

	/**
	 * Clears the map, removing ALL <key, value> pairs from it.
	 */
	public void clear() {
		initBuckets(buckets.length);
		size = 0;
	}

	private void initBuckets(int bucketCount) {
		buckets = new Bucket[bucketCount];
		for (int i = 0; i < bucketCount; i++) {
			buckets[i] = this.new Bucket();
		}
	}

	private int computeBucketIndex(int key) {
		return Math.abs(key) % buckets.length;
	}
}
